Event logic provides a calculus for forming compound event types as expressions over primitive event types. The syntax and semantics of event logic will be described momentarily. Event-logic expressions denote event types, not event occurrences. As such, they do not have truth values. Rather, they are predicates that describe the truth conditions that must hold of an interval for an event to occur. In contrast, an event-occurrence formula does have a truth value. If Φ is an event-logic expression that denotes a primitive or compound event type, and i is an interval, then Φ@i is an atomic event-occurrence formula that is true if and only if the truth conditions for the event type Φ hold of the interval i.
Φ@i denotes coincidental occurrence, the fact that an occurrence of Φ started at the beginning of i and finished at the end of i. Φ@i would not hold if an occurrence of Φ did not precisely coincide with i, but instead overlapped with i. Event types have internal temporal structure that render this distinction important. In the case of primitive event types, that structure is simple. Each primitive event type is derived from a static predicate. A primitive event type Φ holds of an interval if the corresponding static predicate φ holds of every instant in that interval. This means that ({overscore (φ)}@i) and {overscore (φ)}@i might have different truth values. For example, if φ is true of every instant in [0,2) and false of every other instant, then ({overscore (φ)}@[1,3)) is true while {overscore (φ)}@[1, 3) is false. Event logic takes coincidental occurrence to be a primitive notion. As will be demonstrated below, overlapping occurrence is a derived notion that can be expressed in terms of coincidental occurrence using compound event-logic expressions.
Two auxiliary notions are needed to define the syntax and semantics of event logic. First, there are thirteen possible relations between two intervals. These relations are denoted as =, <, >, m, mi, o, oi, s, si, f, fi, d, and di and referred to collectively as Allen relations throughout this disclosure. Second, the span of two intervals i and j, denoted SPAN (i,j), is defined as the smallest super-interval of both i and j.
The syntax of event logic is defined as follows. We are given finite disjoint sets of constant and variable symbols along with a finite set of primitive event-type symbols, each of a specified arity. Constant symbols, such as red-block and hand, denote objects while primitive event-type symbols, such as SUPPORTS, denote parameterized primitive event types. An atomic event-logic expression is a primitive event-type symbol of arity n applied to a sequence of n constants or variables. For example, SUPPORTS (green-block, x). An event-logic expression is either an atomic event-logic expression or one of the compound event-logic expressions Φ, ΦΨ, ∀xΦ, ∃xΦ, ΦR Ψ, or ⋄RΦ, where Φ and Ψare event-logic expressions, x is a variable, andR⊂{=, <, >, m, mi, o, oi, s, si, f, fi, d, di}.
Informally, the semantics of compound event-logic expressions is defined as follows:                Φ denotes the non-occurrence of Φ. An occurrence of Φ coincides with i if no occurrence of Φ coincides with i. Note that (Φ)@i could be true, even if an occurrence of Φ overlapped with i, so long as no occurrence of Φ coincided with i.        ΦΨ denotes the occurrence of either Φ or Ψ.        ∀xΦ denotes the simultaneous occurrence of Φ for all objects.        ∃xΦ denotes the occurrence of Φ for some object.        ΦR Ψ denotes the occurrence of both Φ and Ψ. The occurrences of Φ and Ψ need not be simultaneous. The subscript R specifies a set of allowed Allen relations between the occurrences of Φ and Ψ. If occurrences of Φ and Ψ coincide with i and j respectively, and i r j for some r ε R ,then an occurrence of ΦR Ψ coincides with the span of i and j. The special case Φ{=} Ψ is abbreviated simply as ΦΨ without any subscript. ΦΨ describes an aggregate event where both Φ and Ψ occur simultaneously. The special case Φ{m} Ψ is also abbreviated as (Φ;Ψ. Φ;Ψ describes an aggregate event where an occurrence of Φ is immediately followed by an occurrence of Ψ.        An occurrence of ⋄RΦ coinciding with i denotes an occurrence of Φ at some other interval j such that j r i for some r ε R. ⋄R can act as a tense operator. Expressions such as ⋄{<}Φ, ⋄{>}Φ, ⋄{m}Φ, and ⋄{mi}Φ specify that Φ happened in the noncontiguous past, noncontiguous future, contiguous past, or contiguous future respectively. The ⋄R operator can also be used to derive overlapped occurrence from coincidental occurrence. An occurrence of ⋄{=, o, oi, s, si, f, fi, d, di}Φ coincides with i if an occurrence of Φ overlaps with i. I abbreviate ⋄{=, o, oi, s, si, f, fi, d, di}Φ simply as ⋄Φ without any subscript. Note that while (Φ)@i indicates that no occurrence of Φ coincided with i, (⋄Φ)@i indicates that no occurrence of Φ overlapped with i.        
Formally, the truth of an atomic event-occurrence formula Φ@i is defined relative to a model. Let I be the set of all intervals. A model M is a triple <O,T,P>, where 0 is a set of objects, T is a map from constants and variables to objects from O, and P is map from primitive event-type symbols of arity n to subsets of   I  ×                    O        ×        …        ×        O                    ︸        n              .  P thus maps primitive event-type symbols to relations that take an interval as their first argument, in addition to the remaining object parameters. T[x:=o] denotes a map that is identical to T except that it maps the variable x to the object o. The semantics of event logic is formally defined by specifying an entailment relation MΦ@i as follows:    <O,T,P>p(t1, . . . ,tn)@i if and only if <i, T(t1), . . . ,T(tn)>εP(p).    M(Φ)@i if and only if M|≠Φ@i.    M(ΦΨ)@i if and only if MΦ@i or MΨ@i.    <O,T,P>(∀xΦ)@i if and only if <O,T[x:=o],P>Φ@i for every o ε O.    <O,T,P>(∃xΦ)@i if and only if <O,T[x:=o],P>Φ@i for some o ε O.    M(ΦR Ψ)@i if and only if there exist two intervals j and k such that i=SPAN (j, k), j r k for some r ε R,MΦ@j, and MΨ@k.    M(⋄RΦ)@i if and only if there exists some interval j such that j r i for some r ε R and MΦ@j.
The overall goal of the event-classification component is to infer all occurrences of a given set of compound event types from a given set of primitive event occurrences. Let us define ε(M,Φ) to be {i|MΦ@i}. In principle, ε(M,Φ) could by implemented as a straightforward application of the formal semantics for event logic as specified above. There is a difficulty in doing so, however. Primitive event types often have the property that they are liquid. Liquid events have the following two properties. First, if they are true during an interval i, then they are also true during any subinterval of i. Second, if they are true during two overlapping intervals i and j, then they are also true during SPAN(i,j). When primitive event types are liquid, they will hold over an infinite number of subintervals. This renders the formal semantics inappropriate for a computational implementation. Even if one limits oneself to intervals with integral endpoints, liquid primitive event types will hold over quadratically many subintervals of the scene sequence. And a straightforward computational implementation of the formal semantics would be inefficient. A central result of this disclosure is a novel representation, called spanning intervals, that allows an efficient representation of the infinite sets of subintervals over which liquid event types hold along with an efficient inference procedure that operates on that representation. This representation, and the inference procedure that implements ε(M,Φ), are presented below.